본문으로 건너뛰기

17677 - [1차] 뉴스 클러스터링

정보

풀이 키워드​

스포주의

해시


풀이 코드​

정보
  • 메모리: 92100 KB
  • 시간: 14 ms
import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        // to lowercase
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        
        // set
        Map<String, Integer> A = new HashMap<>();
        Map<String, Integer> B = new HashMap<>();
        Map<String, Integer> I = new HashMap<>();
        Map<String, Integer> U = new HashMap<>();
        
        // init set
        char[] s1Arr = str1.toCharArray();
        char[] s2Arr = str2.toCharArray();
        
        for (int i = 0; i < str1.length()-1; ++i)
            if ('a' <= s1Arr[i] && s1Arr[i] <= 'z' && 'a' <= s1Arr[i+1] && s1Arr[i+1] <= 'z')
                A.merge("" + s1Arr[i] + s1Arr[i+1], 1, Integer::sum);
        
        for (int i = 0; i < str2.length()-1; ++i)
            if ('a' <= s2Arr[i] && s2Arr[i] <= 'z' && 'a' <= s2Arr[i+1] && s2Arr[i+1] <= 'z')
                B.merge("" + s2Arr[i] + s2Arr[i+1], 1, Integer::sum);
        
        // get intersection
        for (String k : A.keySet()) {
            if (B.containsKey(k)) I.put(k, Math.min(A.get(k), B.get(k)));
        }
                
        // get union
        for (String k : A.keySet()) {
            U.put(k, B.containsKey(k) ? Math.max(A.get(k), B.get(k)) : A.get(k));
        }
        for (String k : B.keySet()) {
            if (!U.containsKey(k)) U.put(k, B.get(k));
        }
        
        int a = I.values().stream().mapToInt(i->i).sum();
        int b = U.values().stream().mapToInt(i->i).sum();
        
        if (b == 0) return 65536;
        return (int) (65536 * (double) a / b);
    }
}

풀이 해설​

해시맵을 이용하여 다중집합의 교집합, 합집합을 구하고, 최종적으로 자카드 유사도를 계산하는 문제이다.


✖️ 교집합​

A, B 양 쪽에 모두 존재할때만 min value를 넣는다.

for (String k : A.keySet()) {
    if (B.containsKey(k)) I.put(k, Math.min(A.get(k), B.get(k)));
}

➕ 합집합​

  1. A에만 있으면 A value로 넣는다.
  2. A, B 모두에 있으면 max value로 넣는다.
  3. B에 있으면서 1,2에서 확인하지 않은(=B에만 있는) 값은 B value로 넣는다.
for (String k : A.keySet()) {
    U.put(k, B.containsKey(k) ? Math.max(A.get(k), B.get(k)) : A.get(k));
}
for (String k : B.keySet()) {
    if (!U.containsKey(k)) U.put(k, B.get(k));
}

메모​

  • 무난한 난이도
  • 막줄 a, b 네이밍 별로인듯.. ni, nu가 직관적이고 나을듯